# 第6节 水管工游戏
a = [[0, 0, 0, 0, 0],
     [0, 5, 3, 5, 3],
     [0, 1, 5, 3, 0],
     [0, 2, 3, 5, 1],
     [0, 6, 1, 1, 5],
     [0, 1, 5, 5, 4]]
# print(a)
book = [[0 for i in range(0, 52)] for j in range(0, 52)]
# print(book)
n = 5
m = 4
flag = 0  # 是否找到方案


# 使用栈存储坐标
class Note:

    def __init__(self):
        self.x = 0
        self.y = 0


que = [Note() for i in range(0, 101)]
top = 0
top = 0  # 栈


# 递归函数
def dfs(x, y, front):
    global flag
    global top
    i = 0
    # 判断是否到达终点判断是否到达终点，请注意这里y的坐标是m+1，想一想为什么
    # 另外判断是否到达终点一定要敞在越界判断前面
    if x == n and y == m + 1:
        flag = 1  # 找到了方案
        for index, val in enumerate(que):
            if index > top:
                break
            if index > 0:
                print('(%d,%d)' % (val.x, val.y), end=' ')
        return
    # 越界判断
    if x < 1 or x > n or y < 1 or y > m:
        return
    # 判断管道是否已经使用
    if book[x][y] == 1:
        return
        # 标记管道已经使用
    book[x][y] = 1
    # 入栈
    top += 1
    que[top].x = x
    que[top].y = y
    # 当前管道是直管的情况
    if 5 <= a[x][y] <= 6:
        # 进水口左上右下 1234
        if front == 1:
            dfs(x, y + 1, 1)
        if front == 2:
            dfs(x + 1, y, 2)
        if front == 3:
            dfs(x, y - 1, 3)
        if front == 4:
            dfs(x - 1, y, 4)
    if 1 <= a[x][y] <= 4:
        # 弯管
        if front == 1:
            dfs(x + 1, y, 2)
            dfs(x - 1, y, 4)
        if front == 2:
            dfs(x, y + 1, 1)
            dfs(x, y - 1, 3)
        if front == 3:
            dfs(x - 1, y, 4)
            dfs(x + 1, y, 2)
        if front == 4:
            dfs(x, y + 1, 1)
            dfs(x, y - 1, 3)
    book[x][y] = 0  # 取消标记
    # 取消入栈
    top -= 1


if __name__ == '__main__':
    print('开始搜索')
    dfs(1, 1, 1)
    print()
    print(flag)
    # 打印栈坐标信息
    for q in que:
        if q.x != 0:
            print('(%d,%d)' % (q.x, q.y), end=' ')
